{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Contiguous Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findMaxLength"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #连续数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个二进制数组 <code>nums</code> , 找到含有相同数量的 <code>0</code> 和 <code>1</code> 的最长连续子数组，并返回该子数组的长度。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [0,1]\n",
    "<strong>输出:</strong> 2\n",
    "<strong>说明:</strong> [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [0,1,0]\n",
    "<strong>输出:</strong> 2\n",
    "<strong>说明:</strong> [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= nums.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>nums[i]</code> 不是 <code>0</code> 就是 <code>1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [contiguous-array](https://leetcode.cn/problems/contiguous-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [contiguous-array](https://leetcode.cn/problems/contiguous-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[0,1]', '[0,1,0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        if len(nums) <= 1: return 0\n",
    "        psum = 0\n",
    "        dic = {0:-1}\n",
    "        mlen = 0\n",
    "        for i in range(len(nums)):\n",
    "            psum = psum-1 if nums[i]==0 else psum+1\n",
    "            if psum in dic:\n",
    "                mlen = max(mlen,i-dic[psum])\n",
    "            else:\n",
    "                dic[psum] = i\n",
    "        return mlen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        length = len(nums)\n",
    "        maxlen,count = 0,0\n",
    "        arr = [-2 for _ in range(2*length+1)]\n",
    "        arr[length] = -1\n",
    "        for i in range(length):\n",
    "            count += (-1 if nums[i]==0 else 1)\n",
    "            if arr[count+length] >= -1:\n",
    "                maxlen = max(maxlen,i-arr[count+length])\n",
    "            else:\n",
    "                arr[count+length] = i\n",
    "        return maxlen\n",
    "\n",
    "\n",
    "        # int[] arr = new int[2 * nums.length + 1];\n",
    "        # Arrays.fill(arr, -2);\n",
    "        # arr[nums.length] = -1;\n",
    "        # int maxlen = 0, count = 0;\n",
    "        # for (int i = 0; i < nums.length; i++) {\n",
    "        #     count = count + (nums[i] == 0 ? -1 : 1);\n",
    "        #     if (arr[count + nums.length] >= -1) {\n",
    "        #         maxlen = Math.max(maxlen, i - arr[count + nums.length]);\n",
    "        #     } else {\n",
    "        #         arr[count + nums.length] = i;\n",
    "        #     }\n",
    "\n",
    "        # }\n",
    "        # return maxlen;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        lenth=len(nums)\n",
    "        if not nums or lenth == 1:\n",
    "            return 0\n",
    "        leftdict={}\n",
    "        rightdict={}\n",
    "        rightdict[0]=-1\n",
    "        leftdict[0]=-1\n",
    "        zuo=0\n",
    "        you=0\n",
    "        cha=2*sum(nums)-lenth\n",
    "        if not cha:\n",
    "            return lenth\n",
    "        elif cha > 0:\n",
    "            lmax=0\n",
    "            rmax=0\n",
    "            lmin=float('inf')\n",
    "            rmin=float('inf')\n",
    "            \n",
    "            for i in range(lenth):\n",
    "                zuo += 1 if nums[i] else -1\n",
    "                you += 1 if nums[-i-1] else -1\n",
    "                lmax=max(zuo,lmax)\n",
    "                rmax=max(you,rmax)\n",
    "                #print('4GGG',zuo)\n",
    "                lmin=min(zuo,lmin)\n",
    "                rmin=min(you,rmin)\n",
    "                # print(lmax,rmax)\n",
    "                if zuo not in leftdict:\n",
    "                    leftdict[zuo] = i\n",
    "                if you not in rightdict:\n",
    "                    rightdict[you] = i\n",
    "            #print(leftdict)\n",
    "            #print(rightdict)\n",
    "            zuixiao=float('inf')\n",
    "            for i in range(cha+1):\n",
    "                # print(i)\n",
    "                if i <=lmax and cha-i<= rmax and i >=lmin and cha-i>= rmin:\n",
    "                    zuixiao=min(zuixiao,leftdict[i]+rightdict[cha-i]+2)\n",
    "                    #print(zuixiao)\n",
    "        elif cha < 0:\n",
    "            lmax=0\n",
    "            rmax=0\n",
    "            lmin=float('inf')\n",
    "            rmin=float('inf')\n",
    "            cha=-cha\n",
    "            for i in range(lenth):\n",
    "                zuo += -1 if nums[i] else 1\n",
    "                you += -1 if nums[-i-1] else 1\n",
    "                lmax=max(zuo,lmax)\n",
    "                rmax=max(you,rmax)\n",
    "                lmin=min(zuo,lmin)\n",
    "                rmin=min(you,rmin)\n",
    "                if zuo not in leftdict:\n",
    "                    leftdict[zuo] = i\n",
    "                if you not in rightdict:\n",
    "                    rightdict[you] = i\n",
    "            zuixiao=float('inf')\n",
    "            #print(leftdict)\n",
    "            #print(rightdict)\n",
    "            for i in range(cha+1):\n",
    "                if i <=lmax and cha-i<= rmax and i >=lmin and cha-i>= rmin:\n",
    "                    zuixiao=min(zuixiao,leftdict[i]+rightdict[cha-i]+2)\n",
    "\n",
    "        return lenth-zuixiao"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        memos=[-1]*(2*len(nums)+1)\n",
    "        cur=len(nums)\n",
    "        memos[cur]=0\n",
    "        res=0\n",
    "        for i,num in enumerate(nums):\n",
    "            cur+=2*num-1\n",
    "            if memos[cur]!=-1:\n",
    "                res=max(res,i-memos[cur]+1)\n",
    "            else:\n",
    "                memos[cur]=i+1\n",
    "        return res\n",
    "                \n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        l = len(nums)\n",
    "        temp = [-2] * (l * 2 + 1)\n",
    "\n",
    "        temp[l] = -1\n",
    "\n",
    "        max_len, count = 0, 0\n",
    "\n",
    "        for i in range(l):\n",
    "            if nums[i]:\n",
    "                count += 1\n",
    "            else:\n",
    "                count -= 1\n",
    "            if temp[count + l] >= -1:\n",
    "                max_len = max(max_len, i - temp[count + l])\n",
    "            else:\n",
    "                temp[count + l] = i\n",
    "\n",
    "        return max_len "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        nsize = len(nums)\n",
    "        if nsize < 2:\n",
    "            return 0\n",
    "        \n",
    "        # idx_arr = [ [-1,0] for i in range(2*nsize +1)] ## idx_first, val \n",
    "        idx_arr = [-1 for i in range(2*nsize +1)] ## idx_first\n",
    "        su = 0\n",
    "        max_ = 0\n",
    "        for ix, num in enumerate(nums):\n",
    "            if num == 0:\n",
    "                su += -1\n",
    "            else:\n",
    "                su += 1\n",
    "            if su == 0:\n",
    "                max_ = max(max_, ix+1)\n",
    "                continue\n",
    "            if idx_arr[su + nsize] == -1:\n",
    "                idx_arr[su + nsize] = ix\n",
    "            else:\n",
    "                max_ = max(max_, ix - idx_arr[su + nsize])\n",
    "            '''\n",
    "            if idx_arr[su + nsize][0] == -1:\n",
    "                idx_arr[su + nsize][0] = ix\n",
    "            else:\n",
    "                idx_arr[su + nsize][1]= ix - idx_arr[su + nsize][0]\n",
    "                max_ = max(max_, ix - idx_arr[su + nsize][0])\n",
    "            '''\n",
    "        return max_\n",
    "\n",
    "\n",
    "        '''\n",
    "        czero = 0\n",
    "        cone = 0\n",
    "        max_ = 0\n",
    "        for num in nums:\n",
    "            if num == 0:\n",
    "                czero += 1\n",
    "            else:\n",
    "                cone += 1\n",
    "            if czero == cone:\n",
    "               max_ =  max(max_, czero *2)\n",
    "        \n",
    "        return max_\n",
    "        '''\n",
    "\n",
    "        ## DP... Not DP \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n==1:\n",
    "            return 0\n",
    "        if sum(nums)*2 == n:\n",
    "            return n\n",
    "\n",
    "        hash_set = {0:-1}\n",
    "        counter, res = 0, 0\n",
    "        for idx, num in enumerate(nums):\n",
    "            if num:\n",
    "                counter += 1\n",
    "            else:\n",
    "                counter -= 1\n",
    "            if counter in hash_set:\n",
    "                res = max(res, idx-hash_set[counter])\n",
    "            else:\n",
    "                hash_set[counter] = idx\n",
    "\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        if 2 * sum(nums) == len(nums):\n",
    "            return len(nums)\n",
    "        dic, diff, res = {0:-1}, 0, 0\n",
    "        for i, n in enumerate(nums):\n",
    "            diff += 1 if n == 1 else -1\n",
    "            if diff in dic:\n",
    "                res = max(res, i - dic[diff])\n",
    "            else:\n",
    "                dic[diff] = i\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        if 2 * sum(nums) == len(nums):\n",
    "            return len(nums)\n",
    "        dic, diff, res = {0:-1}, 0, 0\n",
    "        for i, n in enumerate(nums):\n",
    "            diff += 1 if n == 1 else -1\n",
    "            if diff in dic:\n",
    "                res = max(res, i - dic[diff])\n",
    "            else:\n",
    "                dic[diff] = i\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        if nums.count(1) == nums.count(0):\n",
    "            return len(nums)\n",
    "        dp = [0]*len(nums)\n",
    "        if nums[0] == 0:\n",
    "            dp[0] = -1\n",
    "        else:\n",
    "            dp[0] = 1 \n",
    "        addr = dict()\n",
    "        addr[dp[0]] = 0\n",
    "        addr[0] = -1\n",
    "        ans = 0\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i] == 0:\n",
    "                dp[i] = dp[i-1] - 1\n",
    "            else:\n",
    "                dp[i] = dp[i-1] + 1\n",
    "            if dp[i] not in addr:\n",
    "                addr[dp[i]] = i\n",
    "            else:\n",
    "                ans = max(ans,i - addr[dp[i]])\n",
    "\n",
    "        #print(dp)\n",
    "        #print(addr)\n",
    "        return ans\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        n,ans=len(nums),0\n",
    "        count,idx=n+1,[0]*(n*2+5)\n",
    "        idx[n+1]=1\n",
    "        for i in range(n):\n",
    "            count+=1 if nums[i] else -1\n",
    "            if not idx[count]:\n",
    "                idx[count]=i+2\n",
    "            else:\n",
    "                ans=max(ans,i+2-idx[count])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        hash=[-1 for i in range(100000)]\n",
    "        sum=0\n",
    "        max=0\n",
    "        for i in range(0,len(nums)):\n",
    "            if nums[i]==0:\n",
    "                sum-=1\n",
    "            else:\n",
    "                sum+=1\n",
    "            if sum==0:\n",
    "                if i+1>max:max=i+1\n",
    "            if hash[50000-sum]==-1:hash[50000-sum]=i\n",
    "            else:\n",
    "                if i-hash[50000-sum]>max:max=i-hash[50000-sum]\n",
    "        return max\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        if sum(nums) * 2 == len(nums):\n",
    "            return len(nums)\n",
    "        state = 0\n",
    "        starts = {0: -1}\n",
    "        ans = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            state += 1 if num else -1\n",
    "            if state not in starts:\n",
    "                starts[state] = i\n",
    "            elif i - starts[state] > ans:\n",
    "                ans = i - starts[state]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength1(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        if n<2:\n",
    "            return 0\n",
    "        s=sum(nums)\n",
    "        if n%2==0 and s==n//2:\n",
    "            return n\n",
    "        dp=[[0]*n for _ in range(n)]\n",
    "        dp[0][0]=nums[0]\n",
    "        res=0\n",
    "        for i in range(1,n):\n",
    "            for j in range(i+1):\n",
    "                if j==i:\n",
    "                    dp[j][i]=nums[i]\n",
    "                else:\n",
    "                    dp[j][i]=dp[j][i-1]+nums[i]\n",
    "                if (i-j+1)%2==0 and dp[j][i]==(i-j+1)//2:\n",
    "                    res=max(res,i-j+1)\n",
    "        print(dp)\n",
    "        return res\n",
    "\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n < 2:\n",
    "            return 0\n",
    "        s = sum(nums)\n",
    "        if n % 2 == 0 and s == n // 2:\n",
    "            return n\n",
    "        count=0\n",
    "        record={0:-1}\n",
    "        res=0\n",
    "        for i, num in enumerate(nums):\n",
    "            if num:\n",
    "                count+=1\n",
    "            else:\n",
    "                count-=1\n",
    "            if count in record.keys():\n",
    "                prefix=record[count]\n",
    "                res=max(res,i-prefix)\n",
    "            else:\n",
    "                record[count]=i\n",
    "        return res\n",
    "# s=Solution()\n",
    "# print(s.findMaxLength1([0, 0, 1, 0, 0, 0, 1, 1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        pre = 0\n",
    "        has = [-2]*(2*len(nums)+5)\n",
    "        has[n+1] = -1\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            pre += 1 if nums[i] == 1 else -1\n",
    "            if has[pre+n+1] != -2:ans = max(ans,i-has[pre+n+1])\n",
    "            else:has[pre+n+1] = i \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef findMaxLength(self, nums):\n",
    "\t\tp = [-1] + [None] * len(nums)\n",
    "\t\tans, c = 0, 0\n",
    "\t\tfor i, x in enumerate(nums):\n",
    "\t\t\tc += 1 if x == 0 else -1\n",
    "\t\t\tif p[c] is None: p[c] = i\n",
    "\t\t\tans = max(ans, i - p[c])\n",
    "\t\treturn ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        # 前缀和字典: key为1的数量和0的数量的差值,value为对应坐标\n",
    "        hashmap = {0:-1}\n",
    "        # 当前1的数量和0的数量的差值\n",
    "        counter = ans = 0\n",
    "        for i,num in enumerate(nums):\n",
    "            # 每多一个1，差值+1\n",
    "            if num:\n",
    "                counter += 1\n",
    "            # 每多一个0，差值-1\n",
    "            else:\n",
    "                counter -= 1\n",
    "            # 如果存在1和0的数量差值相等的地方，那么说明后者到前者之前1和0的数量相等！\n",
    "            if counter in hashmap:\n",
    "                ans = max(ans, i - hashmap[counter])\n",
    "            else:\n",
    "                hashmap[counter] = i\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        if len(nums) < 2:\n",
    "            return 0\n",
    "\n",
    "        total = 0\n",
    "        max_ = 0\n",
    "        index_dict = [-1000000] * (len(nums) * 2 + 1)\n",
    "        for index in range(len(nums)):\n",
    "            num = nums[index]\n",
    "            if num == 0:\n",
    "                total += 1\n",
    "            else:\n",
    "                total -= 1\n",
    "            \n",
    "            if total == 0:\n",
    "                max_ = max(max_, index + 1)\n",
    "\n",
    "            if index_dict[total + len(nums)] == -1000000:\n",
    "                index_dict[total + len(nums)] = index\n",
    "            else:\n",
    "                max_ = max(max_, index - index_dict[total + len(nums)])\n",
    "        return max_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        dic = {0:-1}\n",
    "        s, ans = 0, 0\n",
    "        for i, x in enumerate(nums):\n",
    "            s += 1 if x == 1 else -1\n",
    "            if s in dic:\n",
    "                ans = max(ans, i - dic[s])\n",
    "            if s not in dic:\n",
    "                dic[s] = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        count = 0\n",
    "        max_len = 0\n",
    "        mapper = {}\n",
    "        mapper[0] = -1\n",
    "        for i in range(len(nums)):\n",
    "            item = nums[i]\n",
    "            if item == 1:\n",
    "                count += 1\n",
    "            else:\n",
    "                count -= 1\n",
    "            \n",
    "            if count in mapper:\n",
    "                max_len = max(max_len, i - mapper[count])\n",
    "            else:\n",
    "                mapper[count] = i\n",
    "\n",
    "        return max_len\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        # require count1==count0\n",
    "        # record diff[i]==the difference of 1 and 0 in nums[:i], i=0 to n\n",
    "        # then nums[left:right] difference is diff[right]-diff[left]\n",
    "        # which equivalent to \"duplicate diff[?]\"\n",
    "        # calculate diff, if first time meet diff, add to dict\n",
    "        # dict record[diff_val]=index of first meet\n",
    "        # if meet same diff_val later,update global max with (right-left)\n",
    "        n=len(nums)\n",
    "        diff=0#for nums[:0]\n",
    "        record={0:-1}\n",
    "        max_len=0#global max length of subarray \n",
    "        for i in range(n):\n",
    "            if nums[i]==1:diff+=1\n",
    "            elif nums[i]==0:diff-=1\n",
    "            # now,record diff\n",
    "            if diff not in record:#only record first appear\n",
    "                record[diff]=i\n",
    "            elif diff in record:#if meet same diff, update global max\n",
    "                max_len=max(max_len,i-record[diff])\n",
    "                \n",
    "        return(max_len)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]==0:\n",
    "                nums[i]=-1\n",
    "        # print(nums) # ok\n",
    "        if sum(nums)==0:\n",
    "            return len(nums)\n",
    "        dic = dict()\n",
    "        ans = -1\n",
    "        temp = 0\n",
    "        for i in range(len(nums)):\n",
    "            temp += nums[i]\n",
    "            if temp==0:\n",
    "                ans = max(ans, i+1)\n",
    "            else:\n",
    "                if temp not in dic.keys():\n",
    "                    dic[temp] = []\n",
    "                    dic[temp].append(i)\n",
    "                else:\n",
    "                    dic[temp].append(i)\n",
    "                if temp in dic.keys():\n",
    "                    dic[temp].sort()\n",
    "                    ans = max(ans, i-dic[temp][0])\n",
    "        return ans\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        d = {}\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "\n",
    "        d[0] = -1\n",
    "        cur = 0\n",
    "        for i in range(n):\n",
    "            if nums[i] == 0:\n",
    "                cur -= 1\n",
    "            if nums[i] == 1:\n",
    "                cur += 1\n",
    "            if cur in d.keys():\n",
    "                ans = max(ans, i - d[cur] )\n",
    "            else:\n",
    "                d[cur] = i\n",
    "        print(d)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        d = {}\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "\n",
    "        d[0] = -1\n",
    "        cur = 0\n",
    "        for i in range(n):\n",
    "            if nums[i] == 0:\n",
    "                cur -= 1\n",
    "            if nums[i] == 1:\n",
    "                cur += 1\n",
    "            if cur in d.keys():\n",
    "                ans = max(ans, i - d[cur] )\n",
    "            else:\n",
    "                d[cur] = i\n",
    "        # print(d)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        count = 0\n",
    "        ans = 0\n",
    "        mp = {}\n",
    "        mp[0] = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == 1:\n",
    "                count = count + 1\n",
    "            elif nums[i] == 0:\n",
    "                count = count - 1\n",
    "            if count in mp:\n",
    "                ans = max(ans, i+1-mp[count])\n",
    "            else:\n",
    "                mp[count] = i+1\n",
    "            print(count)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        pre = 0\n",
    "        # 存储0和-1键值对，这个意思就是前缀和第一个为0的下标是-1，数组的前缀和是累加的，其中一般不会有0存在的，\n",
    "        # 如果出现了0，这是前缀和啊，说明这是从头开始到目前元素和为0的连续子数组，整个这段都是我们需要的长度，这个长度就是目前为0的下标减去\n",
    "        # 第一个储存的和为0的下标。数组下标是从0开始的，当前下标减去-1就是我们需要的长度。这就是为什么要存储{0: -1}键值对\n",
    "        dic = {0: -1}   \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if nums[i] == 0:\n",
    "                pre += -1\n",
    "            else:\n",
    "                pre += nums[i]\n",
    "            if pre not in dic:\n",
    "                dic[pre] = i\n",
    "            else:\n",
    "                tmp = i - dic[pre]\n",
    "                if tmp > ans:\n",
    "                    ans = tmp\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        k = 0\n",
    "        s = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            s[i + 1] = s[i] + ((-1) if nums[i] == 0 else 1)\n",
    "        mp = defaultdict(int)\n",
    "        ans = 0\n",
    "        mp[0] = -1\n",
    "        for i in range(n):\n",
    "            x = s[i + 1]\n",
    "            if x - k in mp:\n",
    "                ans = max(ans, i - mp[x - k] )\n",
    "            if x not in mp:\n",
    "                mp[x] = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        # 把0变成-1\n",
    "        nums = [-1 if num == 0 else 1 for num in nums]\n",
    "        presum = []\n",
    "        t = 0\n",
    "        for num in nums:\n",
    "            t += num\n",
    "            presum.append(t)\n",
    "        \n",
    "        m = defaultdict(int)\n",
    "        m[0] = -1\n",
    "        res = 0\n",
    "        # 前缀和如果之前出现过，那么当前位置减去之前出现的位置就可能是最长的长度\n",
    "        for i in range(len(nums)):\n",
    "            if presum[i] in m:\n",
    "                res = max(res, i - m[presum[i]])\n",
    "            else:\n",
    "                m[presum[i]] = i\n",
    "        return res        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        arr = [-1 if i==0 else 1 for i in nums]\n",
    "        pre= [0]\n",
    "        for num in arr:\n",
    "            pre.append(pre[-1]+num)\n",
    "        # print(arr)\n",
    "        first ={}\n",
    "        longest =0\n",
    "        for i,v in enumerate(pre):\n",
    "            if first.get(v,-1)==-1:\n",
    "                first[v]=i\n",
    "            elif i-first.get(v) >longest:\n",
    "                longest = i-first.get(v)\n",
    "        return longest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1 or 0 not in nums or 1 not in nums:\n",
    "            return 0\n",
    "        \n",
    "        s = [0]\n",
    "        for x in nums: s.append(s[-1] + x)\n",
    "        cnt = Counter()\n",
    "        ans = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] - i / 2 in cnt:\n",
    "                ans = max(ans, i - cnt[s[i] - i / 2])\n",
    "                cnt[s[i] - i / 2] = min(cnt[s[i] - i / 2], i)\n",
    "            else:\n",
    "                cnt[s[i] - i / 2] = i\n",
    "        return ans\n",
    "        '''\n",
    "        begin = nums[0]\n",
    "        combine = []\n",
    "        maxlength = 0\n",
    "        for i in range(0,len(nums)):\n",
    "            print(i)\n",
    "            if i == 0:\n",
    "                count = [1,0]\n",
    "            else:\n",
    "                count = [0,1]\n",
    "            for j in range(i+1,len(nums)):\n",
    "                if nums[j] == 0:\n",
    "                    count[0] += 1\n",
    "                else:\n",
    "                    count[1] += 1\n",
    "                if count[0] == count[1] and count[0] + count[1] > maxlength:\n",
    "                    maxlength = count[0] + count[1]\n",
    "                print(j,count)\n",
    "        return maxlength\n",
    "        '''\n",
    "\n",
    "#[0,0,0,1,1,0,1,1,1,1]\n",
    "\n",
    "        '''\n",
    "        for num in nums:\n",
    "            if current == num:\n",
    "                length += 1\n",
    "            else:\n",
    "                current = num\n",
    "                combine.append(length)\n",
    "                length = 1\n",
    "        combine.append(length)\n",
    "        print(combine)\n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        N = len(nums)\n",
    "        prefix_0 = [0] * (1 + N)\n",
    "        prefix_1 = [0] * (1 + N)\n",
    "        ret = 0\n",
    "        difference_dic = {0: 0}\n",
    "\n",
    "        for i in range(N):\n",
    "            if nums[i] == 0:\n",
    "                prefix_0[i + 1] = prefix_0[i] + 1\n",
    "                prefix_1[i + 1] = prefix_1[i]\n",
    "            else:\n",
    "                prefix_1[i + 1] = prefix_1[i] + 1\n",
    "                prefix_0[i + 1] = prefix_0[i]\n",
    "\n",
    "            diff = prefix_0[i + 1] - prefix_1[i + 1]\n",
    "            if difference_dic.get(diff, None) is None:\n",
    "                difference_dic[diff] = i + 1\n",
    "            else:\n",
    "                j = difference_dic[diff]\n",
    "                ret = max(ret, i + 1 - j)\n",
    "        \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        s0[j]-s0[i-1]=s1[j]-s1[i-1]\n",
    "        s0[j]-s1[j]=s0[i-1]-s1[i-1]\n",
    "        \"\"\"\n",
    "        s0=s1=ans=0\n",
    "        d=defaultdict(list)\n",
    "        d[0]=[0]\n",
    "        for i,x in enumerate(nums,start=1):\n",
    "            if x==0:s0+=1\n",
    "            else:s1+=1\n",
    "            if d[s0-s1]:ans=max(ans,i-d[s0-s1][0])\n",
    "            if d[s0-s1]==[]:d[s0-s1].append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        prefix0 = [0]*(len(nums)+1)\n",
    "        prefix1 = [0]*(len(nums)+1)\n",
    "        for i in range(1,len(prefix0)):\n",
    "            prefix1[i] = prefix1[i-1] + nums[i-1]\n",
    "            prefix0[i] = i - prefix1[i]\n",
    "        hashmap = {}\n",
    "        res = -inf\n",
    "        for i in range(len(prefix0)):\n",
    "            a = prefix0[i] - prefix1[i]\n",
    "            if a in hashmap:\n",
    "                res = max(res,i - hashmap[a])\n",
    "            if a not in hashmap:\n",
    "                hashmap[a] = i \n",
    "        if res < 0:\n",
    "            return 0\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        subtract=dict()\n",
    "        last=0\n",
    "        ret=0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]==0:\n",
    "                last=last-1\n",
    "            else:\n",
    "                last=last+1\n",
    "            if last==0:\n",
    "                ret=max(ret,i+1)\n",
    "            elif last in subtract:\n",
    "                ret=max(ret,i-min(subtract[last]))\n",
    "            if last not in subtract:\n",
    "                subtract[last]=[]\n",
    "            subtract[last].append(i)\n",
    "        \n",
    "        return ret"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
